/* convert newick data to dot graph

bison -d newick.y
	flex newick.l
	gcc -Wall -O3 newick.tab.c lex.yy.c
	echo "((D:10,C:4)D_C,B:4,A:13);" | ./a.out

%{
#include "newick.tab.h"

static size_t string_length=0;
void* saferealloc(void *ptr, size_t size)
        {
        char* p= realloc(ptr,sizeof(char)*(size));
        if(p==NULL)
                {
                fprintf(stderr,"out of memory");
                exit(EXIT_FAILURE);
                }
        return p;
        }
static char* copy(const char* s,size_t length)
        {
        char* p= saferealloc(NULL,sizeof(char)*(length+1));
        strncpy(p,s,length);
        p[length]=0;
        return p;
        }

static char* append(size_t* len,const char* s2,size_t len2)
        {
        yylval.s= saferealloc( yylval.s,sizeof(char)*(*len+len2+1));
        strncpy(&yylval.s[*len],s2,len2);
        yylval.s[*len+len2]=0;
        *len+=len2;
        return yylval.s;
        }

%}

%s apos
%s quot

%%
<quot>{
\\"    append(&string_length,"\"",1);
\'      append(&string_length,"\'",1);
\"      {BEGIN(INITIAL);return STRING;}
}

<apos>{
\\'    append(&string_length,"\'",1);
\"      append(&string_length,"\"",1);
\'      {BEGIN(INITIAL);return STRING;}
}

<apos,quot>{
\n     append(&string_length,"\n",1);
\t     append(&string_length,"\t",1);
\\    append(&string_length,"\",1);
([^\"\'\]|\n)+ append(&string_length,yytext,yyleng);
        }

\:      return COLON;
\;      return SEMICOLON;
\)      return CPAR;
\(      return OPAR;
\,      return COMMA;
\"      {string_length=0;BEGIN(quot); }
\'      {string_length=0;BEGIN(apos); }
[a-zA-Z_][a-zA-Z_0-9]* {yylval.s=copy(yytext,yyleng); return STRING;}
[\+|\-]?[0-9]+  {yylval.d=copy(yytext,yyleng); return NUMBER;}
[\+|\-]?[0-9]+\.[0-9]+([e|E][0-9]+)? {yylval.d=copy(yytext,yyleng); return NUMBER;}
[ \t\n\r]       ;
.       {fprintf(stderr,"Syntax error (%c)\n",yytext[0]);exit(EXIT_FAILURE);}
%%
%{
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
extern int yylex();
extern FILE* yyin;

extern void* saferealloc(void *ptr, size_t size);
int yywrap() { return 1;}
void yyerror(const char* s) {fprintf(stderr,"Error:\"%s\".\n",s);}


struct tree_t
        {
        int id;
        char* label;
        char* length;
        struct tree_t* child;
        struct tree_t* next;
        };

typedef struct tree_t Tree;


static int id_generator=0;
static Tree* newTree()
        {
        Tree* t=saferealloc(0,sizeof(Tree));
        memset(t,0,sizeof(Tree));
        t->id=(++id_generator);
        return t;
        }
static void freeTree(Tree* t)
        {
        if(t==NULL) return;
        free(t->label);
        free(t->length);
        freeTree(t->child);
        freeTree(t->next);
        free(t);
        }

static void escape(FILE* out,const char* s)
        {

        if(s==NULL) { fputs("null",out); return;}
        while(*s!=0)
                {
                switch(*s)
                        {
                        case '\'': fputs("\\'",out); break;
                        case '\"': fputs("\\"",out); break;
                        case '\': fputs("\\",out); break;
                        case '\n': fputs("\n",out); break;
                        case '\r': fputs("\r",out); break;
                        case '\t': fputs("\t",out); break;
                        default : fputc(*s,out); break;
                        }
                ++s;
                }
        }
static void num(FILE* out,const char* d)
        {
        if(d==NULL) { fputs("null",out);; return;}
        fputs(d,out);
        }

static void printTree(FILE* out,const Tree* t)
        {
        fprintf(out,"id%d[label=\"",t->id);
        if(t->label!=NULL) escape(out,t->label);
        if(t->length!=NULL) {if(t->label!=NULL) fputc(':',out);escape(out,t->length);}
        fputs("\"];\n",out);

        if(t->child!=0)
                {
                const Tree* c=t->child;

                while(c!=NULL)
                        {
                        printTree(out,c);
                        fprintf(out,"id%d ->  id%d\n",t->id,c->id);
                        c=c->next;
                        }
                }
        }

%}


%union  {
        char* s;
        char* d;
        struct tree_t* tree;
        }

%error-verbose

%token OPAR
%token CPAR
%token COMMA
%token COLON SEMICOLON 
%token<s> STRING
%token<d> NUMBER
%type<s> label optional_label
%type<d> number optional_length
%type<tree> subtree descendant_list_item descendant_list
%start input
%%

input: descendant_list optional_label optional_length SEMICOLON
        {
        Tree* tree=newTree();
        //tree->type=ROOT;
        tree->child=$1;
        tree->label=$2;
        tree->length=$3;
        fputs("digraph G {\n",stdout);
        printTree(stdout,tree);
        freeTree(tree);
        fputs("}\n",stdout);
        };

descendant_list: OPAR  descendant_list_item CPAR
        {
        $$=$2;
        };

descendant_list_item: subtree
                {
                $$=$1;
                }
        |descendant_list_item COMMA subtree
                {
                Tree* last=$1;
                $$=$1;
                while(last->next!=NULL)
                        {
                        last=last->next;
                        }
                last->next=$3;
                }
        ;

subtree : descendant_list optional_label optional_length
                {
                $$=newTree();
                $$->child=$1;
                $$->label=$2;
                $$->length=$3;
                }
         | label optional_length
                {
                $$=newTree();
                $$->label=$1;
                $$->length=$2;
                }
         ;
 
optional_label:  { $$=NULL;} | label  { $$=$1;};
optional_length:  { $$=NULL;} | COLON number { $$=$2;};
label: STRING { $$=$1;};
number: NUMBER { $$=$1;};



%%

int main(int argc,char** argv)
        {
        yyin=stdin;
        yyparse();
        return EXIT_SUCCESS;
        }

example input:
((D:10,C:4)D_C,B:4,A:13);
*/

digraph G {
id6[label=""];
id3[label="D_C"];
id1[label="D:10"];
id3 ->  id1
id2[label="C:4"];
id3 ->  id2
id6 ->  id3
id4[label="B:4"];
id6 ->  id4
id5[label="A:13"];
id6 ->  id5
}
